package org.example.algorithm.sliding;

import java.util.HashMap;

public class MinWindowSolution {

    public static void main(String[] args) {
        String s = "aaaaaaaaaaaabbbbbcdd";
        String t = "abcdd";
        MinWindowSolution solution = new MinWindowSolution();
        String res = solution.minWindow(s, t);
        System.out.println(res);
    }

    public String minWindow(String s, String t) {
        String res = "";
        if (s.length() < t.length()) {
            return res;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i=0;i<t.length();i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0)+1);
        }
        int left = 0;
        int count = 0;
        int minLen = s.length() + 1;
        while (left < s.length()-t.length()+1 && !map.containsKey(s.charAt(left))) {
            left++;
        }
        int right = left;

        HashMap<Character, Integer> windowMap = new HashMap<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (map.containsKey(c)) {
                count++;
                int charCount = windowMap.getOrDefault(c, 0);
                charCount++;
                windowMap.put(c, charCount);
                if (charCount > map.get(c)) {
                    count = count - 1;
                }
                if (count == t.length()) {
                    while (left < right-t.length()+1) {
                        char leftChar = s.charAt(left);
                        if (map.containsKey(leftChar) && windowMap.get(leftChar) <= map.get(leftChar)) {
                            break;
                        }
                        left++;
                        if (map.containsKey(leftChar) && windowMap.get(leftChar) > map.get(leftChar)) {
                            windowMap.put(leftChar, windowMap.get(leftChar)-1);
                        }
                    }
                    if (minLen > right-left) {
                        minLen = right - left;
                        res = s.substring(left, right);
                    }
                }
            }
        }
        return res;
    }
}
